/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / web / Is_Simple.web

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 20 75 68 72 | 69 67 40 6d 70 69 2d 73 |From uhr|ig@mpi-s|
|00000010| 62 2e 6d 70 67 2e 64 65 | 20 54 75 65 20 4f 63 74 |b.mpg.de| Tue Oct|
|00000020| 20 31 32 20 31 34 3a 33 | 33 3a 31 36 20 31 39 39 | 12 14:3|3:16 199|
|00000030| 33 0a 54 6f 3a 20 73 74 | 65 66 61 6e 0a 43 6f 6e |3.To: st|efan.Con|
|00000040| 74 65 6e 74 2d 4c 65 6e | 67 74 68 3a 20 31 30 36 |tent-Len|gth: 106|
|00000050| 32 0a 58 2d 4c 69 6e 65 | 73 3a 20 36 35 0a 0a 5c |2.X-Line|s: 65..\|
|00000060| 64 6f 63 75 6d 65 6e 74 | 73 74 79 6c 65 5b 31 31 |document|style[11|
|00000070| 70 74 2c 63 6f 6d 6d 65 | 6e 74 73 5d 7b 63 77 65 |pt,comme|nts]{cwe|
|00000080| 62 7d 0a 0a 5c 74 65 78 | 74 77 69 64 74 68 3d 36 |b}..\tex|twidth=6|
|00000090| 2e 35 69 6e 0a 5c 74 65 | 78 74 68 65 69 67 68 74 |.5in.\te|xtheight|
|000000a0| 3d 39 69 6e 0a 5c 6f 64 | 64 73 69 64 65 6d 61 72 |=9in.\od|dsidemar|
|000000b0| 67 69 6e 3d 30 69 6e 0a | 5c 74 6f 70 6d 61 72 67 |gin=0in.|\topmarg|
|000000c0| 69 6e 3d 30 69 6e 0a 0a | 5c 62 65 67 69 6e 7b 64 |in=0in..|\begin{d|
|000000d0| 6f 63 75 6d 65 6e 74 7d | 0a 0a 5c 6d 61 72 6b 72 |ocument}|..\markr|
|000000e0| 69 67 68 74 7b 5c 66 62 | 6f 78 7b 5c 70 72 6f 74 |ight{\fb|ox{\prot|
|000000f0| 65 63 74 5c 74 69 6e 79 | 20 76 65 72 73 69 6f 6e |ect\tiny| version|
|00000100| 20 6f 66 20 5c 74 6f 64 | 61 79 7d 7d 0a 5c 70 61 | of \tod|ay}}.\pa|
|00000110| 67 65 73 74 79 6c 65 7b | 6d 79 68 65 61 64 69 6e |gestyle{|myheadin|
|00000120| 67 73 7d 0a 0a 25 5c 74 | 69 74 6c 65 7b 41 6e 20 |gs}..%\t|itle{An |
|00000130| 49 6d 70 6c 65 6d 65 6e | 74 61 74 69 6f 6e 20 6f |Implemen|tation o|
|00000140| 66 20 52 61 6e 64 6f 6d | 69 7a 65 64 20 53 65 61 |f Random|ized Sea|
|00000150| 72 63 68 20 54 72 65 65 | 73 7d 0a 25 5c 61 75 74 |rch Tree|s}.%\aut|
|00000160| 68 6f 72 7b 4d 61 72 6b | 75 73 20 50 61 75 6c 7d |hor{Mark|us Paul}|
|00000170| 0a 25 5c 64 61 74 65 7b | 5c 74 6f 64 61 79 7d 0a |.%\date{|\today}.|
|00000180| 25 5c 6d 61 6b 65 74 69 | 74 6c 65 0a 0a 25 5c 74 |%\maketi|tle..%\t|
|00000190| 61 62 6c 65 6f 66 63 6f | 6e 74 65 6e 74 73 0a 0a |ableofco|ntents..|
|000001a0| 0a 0a 0a 40 2a 20 54 65 | 73 74 69 6e 67 20 73 69 |...@* Te|sting si|
|000001b0| 6d 70 6c 69 63 69 74 79 | 2e 0a 0a 5c 6e 6f 69 6e |mplicity|...\noin|
|000001c0| 64 65 6e 74 0a 4c 65 74 | 20 24 47 24 20 62 65 20 |dent.Let| $G$ be |
|000001d0| 61 20 67 72 61 70 68 2e | 20 57 65 20 74 65 73 74 |a graph.| We test|
|000001e0| 20 77 68 65 74 68 65 72 | 20 24 47 24 20 69 73 20 | whether| $G$ is |
|000001f0| 73 69 6d 70 6c 65 2c 20 | 69 2e 65 2e 20 63 6f 6e |simple, |i.e. con|
|00000200| 74 61 69 6e 73 20 6e 6f | 0a 70 61 72 61 6c 6c 65 |tains no|.paralle|
|00000210| 6c 20 65 64 67 65 73 2e | 20 54 68 61 74 20 69 73 |l edges.| That is|
|00000220| 20 65 61 73 79 20 74 6f | 20 64 6f 2e 20 57 65 20 | easy to| do. We |
|00000230| 62 75 63 6b 65 74 2d 73 | 6f 72 74 20 74 68 65 20 |bucket-s|ort the |
|00000240| 65 64 67 65 73 20 74 77 | 69 63 65 3a 0a 6f 6e 63 |edges tw|ice:.onc|
|00000250| 65 20 61 63 63 6f 72 64 | 69 6e 67 20 74 6f 20 74 |e accord|ing to t|
|00000260| 68 65 69 72 20 73 6f 75 | 72 63 65 20 6e 6f 64 65 |heir sou|rce node|
|00000270| 20 61 6e 64 20 6f 6e 63 | 65 20 61 63 63 6f 72 64 | and onc|e accord|
|00000280| 69 6e 67 20 74 6f 20 74 | 68 65 69 72 20 74 61 72 |ing to t|heir tar|
|00000290| 67 65 74 0a 6e 6f 64 65 | 2e 20 53 69 6e 63 65 20 |get.node|. Since |
|000002a0| 62 75 63 6b 65 74 20 73 | 6f 72 74 20 69 73 20 73 |bucket s|ort is s|
|000002b0| 74 61 62 6c 65 20 74 68 | 69 73 20 77 69 6c 6c 20 |table th|is will |
|000002c0| 63 6f 6c 6c 65 63 74 20 | 70 61 72 61 6c 6c 65 6c |collect |parallel|
|000002d0| 20 65 64 67 65 73 2e 0a | 0a 40 63 0a 0a 62 6f 6f | edges..|.@c..boo|
|000002e0| 6c 20 69 73 5f 73 69 6d | 70 6c 65 28 67 72 61 70 |l is_sim|ple(grap|
|000002f0| 68 26 20 47 29 0a 0a 7b | 0a 6c 69 73 74 3c 65 64 |h& G)..{|.list<ed|
|00000300| 67 65 3e 65 6c 3d 20 47 | 2e 61 6c 6c 5f 65 64 67 |ge>el= G|.all_edg|
|00000310| 65 73 28 29 3b 0a 6e 6f | 64 65 20 76 3b 0a 0a 65 |es();.no|de v;..e|
|00000320| 64 67 65 20 65 3b 0a 69 | 6e 74 20 6e 3d 20 30 3b |dge e;.i|nt n= 0;|
|00000330| 0a 0a 6e 6f 64 65 5f 61 | 72 72 61 79 3c 69 6e 74 |..node_a|rray<int|
|00000340| 3e 20 6e 75 6d 28 47 29 | 3b 0a 66 6f 72 61 6c 6c |> num(G)|;.forall|
|00000350| 5f 6e 6f 64 65 73 28 76 | 2c 47 29 20 6e 75 6d 5b |_nodes(v|,G) num[|
|00000360| 76 5d 3d 20 6e 2b 2b 3b | 0a 0a 6e 75 6d 5f 70 74 |v]= n++;|..num_pt|
|00000370| 72 3d 20 26 6e 75 6d 3b | 0a 0a 65 6c 2e 62 75 63 |r= &num;|..el.buc|
|00000380| 6b 65 74 5f 73 6f 72 74 | 28 30 2c 6e 2d 31 2c 26 |ket_sort|(0,n-1,&|
|00000390| 65 70 65 5f 73 6f 75 72 | 63 65 5f 6e 75 6d 29 3b |epe_sour|ce_num);|
|000003a0| 0a 65 6c 2e 62 75 63 6b | 65 74 5f 73 6f 72 74 28 |.el.buck|et_sort(|
|000003b0| 30 2c 6e 2d 31 2c 26 65 | 70 65 5f 74 61 72 67 65 |0,n-1,&e|pe_targe|
|000003c0| 74 5f 6e 75 6d 29 3b 0a | 0a 69 6e 74 20 69 3d 20 |t_num);.|.int i= |
|000003d0| 2d 31 3b 0a 69 6e 74 20 | 6a 3d 20 2d 31 3b 0a 0a |-1;.int |j= -1;..|
|000003e0| 66 6f 72 61 6c 6c 28 65 | 2c 65 6c 29 0a 7b 20 69 |forall(e|,el).{ i|
|000003f0| 66 28 6a 3d 3d 6e 75 6d | 5b 73 6f 75 72 63 65 28 |f(j==num|[source(|
|00000400| 65 29 5d 26 26 69 3d 3d | 6e 75 6d 5b 74 61 72 67 |e)]&&i==|num[targ|
|00000410| 65 74 28 65 29 5d 29 0a | 20 20 72 65 74 75 72 6e |et(e)]).|  return|
|00000420| 20 66 61 6c 73 65 3b 0a | 20 20 65 6c 73 65 0a 20 | false;.|  else. |
|00000430| 20 7b 20 6a 3d 20 6e 75 | 6d 5b 73 6f 75 72 63 65 | { j= nu|m[source|
|00000440| 28 65 29 5d 3b 0a 20 20 | 20 20 69 3d 20 6e 75 6d |(e)];.  |  i= num|
|00000450| 5b 74 61 72 67 65 74 28 | 65 29 5d 3b 0a 20 20 7d |[target(|e)];.  }|
|00000460| 0a 7d 0a 72 65 74 75 72 | 6e 20 74 72 75 65 3b 0a |.}.retur|n true;.|
|00000470| 0a 7d 0a 0a 40 20 5c 65 | 6e 64 7b 64 6f 63 75 6d |.}..@ \e|nd{docum|
|00000480| 65 6e 74 7d 0a 0a       |                         |ent}..  |        |
+--------+-------------------------+-------------------------+--------+--------+